package com.bee.剑指offer;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 *
 * @version 1.0.0s
 * @Author yong.Mr
 * @data 2021-03-11
 */
public class 重建二叉树 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }

    public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(null == pre || null == in){
            return null;
        }
        if(pre.length != in.length){
            return null;
        }
        TreeNode root = null;
        for (int i = 0; i < in.length; i++) {
             if(pre[0] == in[i]) {
                 root = new TreeNode(pre[0]);

                 int[] pre2 = new int[i];
                 int[] in2 = new int[i];
                 for (int j = 1; j < i + 1; j++) {
                     pre2[j - 1] = pre[j];
                 }

                 for (int j = 0; j < i; j++) {
                     in2[j] = in[j];
                 }
                 root.left = reConstructBinaryTree(pre2, in2);
                 int[] rightPre = new int[pre.length - i - 1];
                 int[] rightIn = new int[pre.length - i - 1];
                 int h = 0;
                 int k = 0;
                 for (int j = i + 1; j < pre.length; j++) {
                     rightPre[h++] = pre[j];
                 }
                 for (int j = i + 1; j < in.length; j++) {
                     rightIn[k++] = in[j];
                 }
                 root.right = reConstructBinaryTree(rightPre, rightIn);
             }
        }
        return root;
    }

    private static List<Integer> preList = new ArrayList<Integer>();
    private static List<Integer> inList = new ArrayList<Integer>();
    private static List<Integer> afterList = new ArrayList<Integer>();

    /**
     * 先序遍历
     * 先根，再左，再右
     */
    public static void preRound(TreeNode root){
        if(root!= null){
            preList.add(root.val);
            preRound(root.left);
            preRound(root.right);
        }
    }
    /**
     * 中序遍历
     * 先左，再根，再右
     */
    public static void inRound(TreeNode root){
        if(root!= null){
            inRound(root.left);
            inList.add(root.val);
            inRound(root.right);
        }
    }

    /**
     * 后序遍历
     * 先左，再右，再根
     */
    public static void afterRound(TreeNode root){
        if(root!= null){
            afterRound(root.left);
            afterRound(root.right);
            afterList.add(root.val);
        }
    }

    /**
     * 层次遍历，
     * 一层层的获取数据
     */
    public static void layerRound(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new ArrayDeque();
        queue.offer(root);
        // 二叉树的深度，也可以使用遍历二数获取数的深度
        int depth = 0;
        // 二叉树的总结点
        int nodeCount = 0;
        // 叶子结点数量
        int countLeaf = 0;
        while (!queue.isEmpty()) {
            int n = queue.size();
            List<Integer> list = new ArrayList<Integer>();
            depth++;
            nodeCount += n;
            for (int i = 0; i < n; i++) {
                TreeNode poll = queue.poll();
                list.add(poll.val);
                if(poll.left != null) {
                    queue.offer(poll.left);
                }
                if(poll.right != null) {
                    queue.offer(poll.right);
                }
                if(poll.left == null && poll.right == null) {
                    countLeaf++;
                }
            }
            result.add(list);
        }
        System.out.println(result);
    }

    /**
     * 计算二叉树的深度
     * @param root
     */
    public static int Depth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int m = Depth(root.left);
        int n = Depth(root.right);
        return m > n ? m+1:n+1;
    }

    private static Integer nodeCounts = 0;
    /**
     * 计算二叉树节点总个数
     * @param root
     */
    public static void NodeCount(TreeNode root) {
        if(root == null) {
            return;
        }
        nodeCounts++;
        NodeCount(root.left);
        NodeCount(root.right);
    }

    private static Integer leafNodeCount = 0;
    /**
     * 计算二叉树叶子节点总个数
     * @param root
     */
    public static void leafNodeCount(TreeNode root) {
        if(root == null) {
            return;
        }
        if(root.left == null && root.right == null) {
            leafNodeCount++;
        }
        leafNodeCount(root.left);
        leafNodeCount(root.right);
    }

    /**
     * 复制二叉树：深度复制
     */
    public static int Copy(TreeNode old, TreeNode newTree){
        if (old == null) {
            return 0;
        }
        newTree = new TreeNode(old.val);
        Copy(old.left,newTree.left);
        Copy(old.right,newTree.right);
        return 1;
    }


    public static void main(String[] args) {
        TreeNode treeNode = reConstructBinaryTree(new int[]{1,2,4,7,3,5,6,8}, new int[]{4,7,2,1,5,3,8,6});
        preRound(treeNode);
        System.out.println(preList.toString());
        inRound(treeNode);
        System.out.println(inList.toString());
        afterRound(treeNode);
        System.out.println(afterList.toString());
        layerRound(treeNode);
    }
}


